Network Security Public Key Cryptography

John

1. Introduction: The Security Landscape

๐ŸŽฏ Course Context

This lecture focuses on securing communication at different layers of the IP/TCP stack. We can implement security at:

  • Network Level: IPsec (encrypts IP packets)
  • Transport Level: SSL/TLS (encrypts application data)

The Real-World Communication Challenge

Consider the modern internet: billions of clients need to communicate securely with millions of servers. Every time you access a website, check email, or make an online purchase, secure communication is required.

๐Ÿ“ฑ Example: Online Banking

When you log into your bank account:

  • Your phone/computer (client) needs to securely communicate with the bank’s server
  • Your credentials must be encrypted so attackers can’t intercept them
  • The bank needs to verify it’s really you
  • You need to verify you’re connected to the real bank (not a phishing site)

This scenario repeats billions of times daily across the globe!

2. Why We Need Public Key Cryptography

The Limitations of Symmetric Cryptography

Symmetric cryptography works well for confidentiality and integrity:

  • Confidentiality: Stream ciphers, block ciphers with encryption modes
  • Integrity: Message Authentication Codes (MACs)

โš ๏ธ Critical Problem: Key Distribution

The fundamental limitation: Sender and receiver must share the same secret key.

This creates three major challenges:

  1. Secure Channel Required: How do you securely share the key initially?
  2. No Prior Relationship: Impossible for two parties who have never met
  3. Scalability Crisis: For n parties to communicate, we need n(n-1)/2 different keys!

๐Ÿ“Š Example: The Key Explosion Problem

Let’s calculate keys needed for symmetric cryptography:

  • 5 people: 5ร—4/2 = 10 keys needed
  • 100 people: 100ร—99/2 = 4,950 keys needed
  • 1,000 people: 1,000ร—999/2 = 499,500 keys needed
  • 1 million users: ~500 billion keys needed! ๐Ÿคฏ

Each client connecting to a server would need a unique shared key. This is completely impractical at internet scale.

The Public Key Cryptography Solution

Public key cryptography revolutionized secure communication by introducing a brilliant concept: two mathematically related but different keys.

๐Ÿ”‘ Core Principle of PKC

Each person has a key pair:

  • Public Key: Published openly, anyone can access it
  • Private Key: Kept secret, known only to the owner

Mathematical Magic: What one key encrypts, only the other can decrypt. However, knowing the public key doesn’t reveal the private key!

๐Ÿ”’ Example: Sending a Confidential Message

Scenario: Alice wants to send a secret message to Bob.

  1. Bob publishes his public key (available to everyone, including Alice)
  2. Alice obtains Bob’s public key from a public directory
  3. Alice encrypts her message using Bob’s public key
  4. Alice sends the encrypted message over the internet (even attackers can intercept it)
  5. Only Bob can decrypt it using his private key

Security Guarantee: Even if an attacker intercepts the encrypted message and has Bob’s public key, they cannot decrypt it without Bob’s private key!

โœ… Advantages of PKC

  • No Shared Secrets: Two parties can communicate securely without prior key exchange
  • Scalability: Each person needs only ONE key pair regardless of how many people they communicate with
  • Key Distribution: Solves the “chicken-or-egg” problem – no secure channel needed to exchange keys
  • Open Environments: Perfect for the internet where parties have no prior relationship
  • Non-repudiation: Digital signatures provide proof of who sent a message

โŒ Disadvantages of PKC

  • Slow: 2-3 orders of magnitude slower than symmetric crypto (1000x slower!)
  • Larger Keys: 2048+ bits (RSA) vs 256 bits (AES)
  • Mathematical Assumptions: Security relies on unproven number theory problems
  • Complexity: More complex to implement correctly
  • Key Authenticity: Still need to verify public keys actually belong to claimed owners (PKI problem)

Historical Context

๐Ÿ“œ History of Public Key Cryptography

  • 1970: James Ellis (British GCHQ) – Proposed public-key encryption in classified paper (revealed 1997)
  • 1976: Diffie & Hellman – Published “New Directions in Cryptography”
    • Introduced concept of public-key encryption schemes
    • Proposed Diffie-Hellman key agreement protocol
    • Introduced digital signatures concept
  • 1978: Rivest, Shamir, Adleman – Invented RSA, first practical PKC system

3. Public Key Encryption Fundamentals

The Three Primitives of PKC

Public key cryptography provides three fundamental operations:

1๏ธโƒฃ Public Key Encryption

Purpose: Send confidential messages

How it works: Encrypt with recipient’s public key, decrypt with recipient’s private key

Examples: RSA-OAEP, El Gamal, DHIES/ECIES

2๏ธโƒฃ Digital Signatures

Purpose: Prove who sent a message (authentication + non-repudiation)

How it works: Sign with sender’s private key, verify with sender’s public key

Examples: RSA signatures, (EC-)DSA, Schnorr

3๏ธโƒฃ Key Exchange/Agreement

Purpose: Establish a shared session key securely

How it works: Use public key operations to agree on a symmetric key, then use fast symmetric crypto for the session

Examples: Diffie-Hellman Exchange (DHE in TLS), ntor (Tor protocol)

๐Ÿ” Example: How HTTPS Uses PKC

When you visit a secure website (https://), here’s what happens behind the scenes:

  1. Key Exchange: Your browser and the server use public key cryptography (typically DHE or RSA) to establish a shared session key
  2. Switch to Symmetric: Once the session key is established, all further communication uses fast AES encryption with that session key
  3. Digital Signatures: The server’s public key is signed by a Certificate Authority to prove authenticity

Why this hybrid approach? Get the key distribution benefits of PKC with the speed of symmetric cryptography!

4. RSA Cryptosystem: The Mathematics

Essential Number Theory Background

Before understanding RSA, we need a few mathematical concepts:

๐Ÿ“ Number Theory Foundations

1. Relatively Prime Numbers (Coprime):

Two numbers are relatively prime if their greatest common divisor (gcd) is 1.

gcd(a, b) = 1 โŸน a and b are relatively prime

Example: gcd(15, 28) = 1, so 15 and 28 are relatively prime

2. Euler’s Totient Function ฯ†(n):

ฯ†(n) counts how many integers from 1 to n are relatively prime to n

  • For prime p: ฯ†(p) = p – 1
  • For n = pร—q where p, q are primes: ฯ†(n) = (p-1)(q-1)

3. Euler’s Theorem:

If a โˆˆ โ„คn*, then aฯ†(n) โ‰ก 1 (mod n)

4. Fermat’s Little Theorem (Special Case):

If p is prime and gcd(a,p) = 1, then ap-1 โ‰ก 1 (mod p)

๐Ÿงฎ Example: Computing ฯ†(n)

Let’s compute ฯ†(15):

  • 15 = 3 ร— 5 (both prime)
  • ฯ†(15) = (3-1) ร— (5-1) = 2 ร— 4 = 8
  • Indeed, integers from 1 to 15 that are coprime to 15: {1, 2, 4, 7, 8, 11, 13, 14} = 8 numbers โœ“

RSA Key Generation

RSA Key Generation Algorithm

Input: Desired security level (typically 2048 or 4096 bits)

Output: Public key (e, n) and Private key d

  1. Generate two large primes p and q
    • Each should be at least 1024 bits (for 2048-bit security)
    • Use primality testing (Miller-Rabin test)
  2. Compute n = p ร— q
    • n is the modulus (2048+ bits)
    • Note: ฯ†(n) = (p-1)(q-1)
  3. Choose e (public exponent)
    • e must be relatively prime to ฯ†(n)
    • Typically e = 3 or e = 65537 (216 + 1)
    • e = 3 is fast but may have vulnerabilities
  4. Compute d (private exponent)
    • Find d such that: e ร— d โ‰ก 1 (mod ฯ†(n))
    • d is the modular multiplicative inverse of e
    • Use Extended Euclidean Algorithm
  5. Publish (e, n) as public key
  6. Keep d secret as private key
  7. Securely destroy p, q, and ฯ†(n)

๐Ÿ”ข Example: Small RSA (Educational Only!)

Note: This uses tiny numbers for illustration. Real RSA uses 2048+ bit numbers!

Key Generation:

  1. Choose p = 11, q = 7
  2. Compute n = 11 ร— 7 = 77
  3. Compute ฯ†(n) = (11-1)(7-1) = 10 ร— 6 = 60
  4. Choose e = 37 (verify gcd(37, 60) = 1 โœ“)
  5. Compute d = 13 (verify 37 ร— 13 = 481 โ‰ก 1 mod 60 โœ“)
  6. Public key: (e=37, n=77)
  7. Private key: d=13

Encryption: Let’s encrypt message M = 15

C = Me mod n = 1537 mod 77 = 71

Decryption: Recover M from C = 71

M = Cd mod n = 7113 mod 77 = 15 โœ“

It works! The original message 15 is recovered!

Why RSA Decryption Works: The Mathematical Proof

๐ŸŽ“ Proof Sketch

  1. By definition: eยทd โ‰ก 1 (mod ฯ†(n))
  2. Therefore: eยทd = 1 + kยทฯ†(n) = 1 + k(p-1)(q-1) for some integer k
  3. If gcd(m, p) = 1, then by Fermat’s Little Theorem: mp-1 โ‰ก 1 (mod p)
  4. Raise both sides to power k(q-1) and multiply by m:
    5. m1+k(p-1)(q-1) โ‰ก m (mod p)
  5. Therefore: med โ‰ก m (mod p)
  6. By the same argument: med โ‰ก m (mod q)
  7. Since p and q are distinct primes and n = pยทq:
    8. med โ‰ก m (mod n)
  8. Conclusion: (me)d โ‰ก m (mod n), so decryption recovers the original message!

5. RSA Security Analysis

Security Foundations

RSA security relies on two fundamental computational problems:

1๏ธโƒฃ The Factoring Problem

Problem: Given a large number n, find its prime factors p and q

Why it’s hard: No known efficient algorithm for factoring large numbers exists

Impact on RSA: If you can factor n, you can compute ฯ†(n) = (p-1)(q-1), then compute d from e, breaking RSA completely

2๏ธโƒฃ The RSA Problem

Problem: Given (n, e) and ciphertext C, find M such that Me โ‰ก C (mod n)

Why it’s hard: Requires taking the eth root modulo n, no efficient algorithm known

Relationship: Factoring โŸน RSA problem solvable, but maybe RSA problem could be solved without factoring (not proven either way)

Factoring Progress Timeline

โš ๏ธ RSA Factoring Challenge – Historical Progress

Year Bits Factored Implication
2007 700 bits 1024-bit RSA considered potentially vulnerable
2009 768 bits 1024-bit RSA officially deprecated
2019 795 bits Factoring capabilities steadily improving
2020 829 bits Approaching 1024-bit threshold

Current Recommendations (2026):

  • Minimum: 2048 bits (considered secure for near-term)
  • Recommended: 3072 bits (secure for medium-term)
  • Long-term: 4096 bits or higher
  • NIST Equivalent: 15360-bit RSA โ‰ˆ 256-bit symmetric security

The Performance Trade-off

โšก Computational Complexity

RSA operations scale quadratically with key length

  • 2048-bit RSA is 4ร— slower than 1024-bit RSA
  • 4096-bit RSA is 16ร— slower than 1024-bit RSA
  • RSA is 100-1000ร— slower than AES-256

Why RSA is slow:

  • Modular exponentiation with huge numbers (2048+ bits)
  • Encryption: compute me mod n
  • Decryption: compute cd mod n (d is typically very large)

๐Ÿ’ก Example: Hybrid Encryption (How SSL/TLS Works)

Because RSA is slow, real systems use hybrid encryption:

  1. RSA for Key Exchange:
    • Client generates random AES-256 key (32 bytes)
    • Client encrypts this key with server’s RSA public key
    • Send encrypted key to server (one RSA operation)
  2. AES for Data:
    • Both parties now share the AES session key
    • All further communication uses fast AES encryption
    • Can send gigabytes at high speed!

Result: Get security of RSA with speed of AES! Best of both worlds!

6. Advanced Security: CPA and CCA

Security Notions for Encryption

Not all encryption schemes are created equal. Modern cryptography defines precise security levels:

๐Ÿ”’ CPA Security (Chosen Plaintext Attack)

Threat Model: Attacker has access to an encryption oracle

  • Attacker can encrypt any messages they choose
  • Attacker sees the resulting ciphertexts
  • Goal: Distinguish between encryptions of two chosen messages

Also called Semantic Security: Knowing the ciphertext (and its length) reveals no information about the plaintext beyond its length

๐Ÿ›ก๏ธ CCA Security (Chosen Ciphertext Attack)

Threat Model: Attacker has access to both encryption AND decryption oracles

  • Attacker can encrypt any messages (like CPA)
  • Attacker can also decrypt any ciphertexts (except the challenge ciphertext)
  • This is a very strong attack model!

Why this matters: CCA security prevents sophisticated attacks where attackers manipulate ciphertexts to learn information

Why Textbook RSA Fails CPA Security

โš ๏ธ Textbook RSA is NOT CPA-Secure!

Problem 1: Deterministic

The same message always produces the same ciphertext:

  • Attacker can guess plaintext, compute ciphertext, compare
  • If message space is small (like “Yes”/”No”), attacker can build a lookup table

Problem 2: Malleable (Can Tamper)

RSA has multiplicative property:

If C = Me, then (C ยท Xe) = (M ยท X)e

Attacker can modify encrypted auction bids:

  • Intercept encrypted bid C = bide
  • Compute X = (101/100)e mod n
  • Submit C’ = C ยท X = (bid ร— 1.01)e
  • Server decrypts to bid ร— 1.01 (1% higher!)

๐ŸŽฏ Example: Dictionary Attack on Textbook RSA

Scenario: Patient sends encrypted medical diagnosis to insurance

  • Message space: {Healthy, Diabetes, Cancer, Heart Disease}
  • Attacker intercepts ciphertext C

Attack:

  1. Attacker encrypts “Healthy” using public key โ†’ Cโ‚
  2. Attacker encrypts “Diabetes” using public key โ†’ Cโ‚‚
  3. Attacker encrypts “Cancer” using public key โ†’ Cโ‚ƒ
  4. Attacker encrypts “Heart Disease” using public key โ†’ Cโ‚„
  5. Compare C with {Cโ‚, Cโ‚‚, Cโ‚ƒ, Cโ‚„}
  6. If C = Cโ‚ƒ, patient has cancer! ๐Ÿ˜ฑ

Privacy completely broken! This is why textbook RSA is never used in practice.

Making RSA CPA-Secure: Padded RSA

Padded RSA Encryption (CPA-Secure)

Key Generation: Same as standard RSA โ†’ Public key (e, n), Private key d

Encryption of message m:

  1. Choose random r โˆˆ {0,1}||n|| – โ„“(ฮบ) – 1
  2. Concatenate: mฬ‚ = r || m (random padding || message)
  3. Compute ciphertext: c = mฬ‚e (mod n)

Decryption of ciphertext c:

  1. Compute mฬ‚ = cd (mod n)
  2. Extract the โ„“(ฮบ) lower-order bits as message m

Security: CPA-secure assuming RSA problem is hard

Weakness: Vulnerable to CCA attacks! Still not good enough for real systems.

RSA-OAEP: CCA-Secure RSA

The industry standard for RSA encryption is RSA-OAEP (Optimal Asymmetric Encryption Padding):

๐Ÿ” RSA-OAEP: Production-Grade RSA

Key Features:

  • Uses two hash functions G and H (modeled as random oracles)
  • Applies complex padding scheme with randomness
  • Provides CCA security (strongest security notion)
  • Used in TLS, PGP, and other real-world systems

Mathematical Details: (Not important for understanding, but included for completeness)

  1. Choose random r โˆˆ {0,1}||n/2||
  2. Set m’ = m || 0||n/4||
  3. Compute mฬ‚โ‚ = G(r) โŠ• m’
  4. Compute mฬ‚ = mฬ‚โ‚ || (r โŠ• H(mฬ‚โ‚))
  5. Encrypt: c = mฬ‚e (mod n)

Why it’s secure: The complex padding makes it impossible for attackers to create valid decryptions or manipulate ciphertexts meaningfully.

โœ… Example: Dictionary Attack FAILS on RSA-OAEP

Same scenario as before, but using RSA-OAEP:

Attack Attempt:

  1. Attacker encrypts “Cancer” using public key โ†’ Cโ‚
  2. Attacker encrypts “Cancer” again โ†’ Cโ‚‚
  3. Cโ‚ โ‰  Cโ‚‚ due to random padding!
  4. Intercepted ciphertext C matches neither Cโ‚ nor Cโ‚‚
  5. Attack fails! Privacy preserved! โœ“

7. Digital Signatures: Authentication & Non-Repudiation

The Problem: How to Sign Digital Documents

In the physical world, handwritten signatures provide:

  • Authentication: Proves who signed
  • Integrity: Signature can’t be moved to different document
  • Non-repudiation: Signer can’t deny they signed

๐Ÿ“ Example: Credit Card Signature

When you pay with a credit card:

  1. You sign the receipt
  2. Merchant compares signature on receipt to signature on card
  3. If they match โ†’ payment authorized
  4. You can’t later claim “I didn’t buy this!” because you signed

Question: Can we do this digitally?

โš ๏ธ Why MAC is NOT Sufficient

Message Authentication Codes (MAC) provide:

  • โœ“ Integrity (message wasn’t modified)
  • โœ“ Authentication (message came from someone with the key)
  • โœ— NO non-repudiation

The Problem: Both sender AND receiver have the same key!

  • Alice could compute MAC for message to Bob
  • Bob could also compute MAC for the same message (he has the key too)
  • If dispute arises, judge can’t tell who created the MAC
  • Either party could have created it!

Digital Signatures: The Solution

๐Ÿ–‹๏ธ Digital Signature Concept

Core Idea: Use public key cryptography “in reverse”

  • Signing: Use your private key (only you can do this)
  • Verification: Anyone can verify using your public key

A Digital Signature Scheme Consists Of:

  1. Key Generation: Create public/private key pair
  2. Signing Algorithm: Takes message + private key โ†’ signature
  3. Verification Algorithm: Takes message + signature + public key โ†’ valid/invalid

Security Properties:

  • Authentication: Only someone with private key could create signature
  • Integrity: Signature is tied to specific message
  • Non-repudiation: Signer can’t deny signing (private key is secret!)

RSA Signatures

RSA Signature Scheme

Key Generation:

  • Generate RSA keys as before: public key (e, n), private key d
  • Signing key: d (private)
  • Verification key: (e, n) (public)

Signing message m:

  1. Compute hash: h = hash(m)
  2. Sign hash: s = hd mod n
  3. Output signature: s

Verifying signature s on message m:

  1. Compute hash: h = hash(m)
  2. Verify: se mod n =? h
  3. If equal โ†’ valid signature โœ“
  4. If not equal โ†’ invalid signature โœ—

Note: Signing โ‰ˆ decryption operation, Verification โ‰ˆ encryption operation

โœ๏ธ Example: Signing a Contract

Scenario: Alice wants to sign a digital contract with Bob

Setup:

  • Alice’s public key: (e, n) = (37, 77)
  • Alice’s private key: d = 13
  • Contract message: “I agree to pay Bob $1000”

Signing Process:

  1. Alice computes hash: h = hash(“I agree to pay Bob $1000”) = 52 (simplified)
  2. Alice signs: s = 5213 mod 77 = 31
  3. Alice sends to Bob: (message, signature) = (“I agree to pay Bob $1000”, 31)

Bob’s Verification:

  1. Bob computes hash: h = hash(“I agree to pay Bob $1000”) = 52
  2. Bob verifies: 3137 mod 77 = 52 โœ“
  3. Valid signature! Contract is authenticated!

Later, if dispute arises:

  • Judge can verify signature using Alice’s public key
  • Only Alice could have created this signature (only she has private key)
  • Alice can’t deny signing โ†’ non-repudiation!

Why Must We Hash the Message?

โš ๏ธ Critical: Always Hash Before Signing!

Attack on RSA Signatures Without Hashing:

  1. Attacker obtains two signed messages:
    • Message mโ‚ with signature sโ‚ = mโ‚d mod n
    • Message mโ‚‚ with signature sโ‚‚ = mโ‚‚d mod n
  2. Attacker computes: sโ‚ƒ = sโ‚ ร— sโ‚‚ mod n
  3. This gives: sโ‚ƒ = mโ‚d ร— mโ‚‚d = (mโ‚ ร— mโ‚‚)d mod n
  4. Attacker has forged signature on mโ‚ƒ = mโ‚ ร— mโ‚‚!

Why Hashing Prevents This:

  • With hashing: sโ‚ = hash(mโ‚)d, sโ‚‚ = hash(mโ‚‚)d
  • sโ‚ ร— sโ‚‚ = (hash(mโ‚) ร— hash(mโ‚‚))d
  • But hash(mโ‚) ร— hash(mโ‚‚) โ‰  hash(mโ‚ƒ) for any mโ‚ƒ!
  • Attacker can’t find any message that corresponds to this signature
  • Forgery prevented! โœ“

Security Requirements for Digital Signatures

๐Ÿ›ก๏ธ Existential Unforgeability Under Adaptive Chosen-Message Attack

This is the gold standard for digital signature security. It means:

Existential Forgery:

  • Attacker succeeds if they forge a valid signature on ANY message
  • Even if the message is gibberish or chosen by attacker
  • Attacker has little control over what message they can forge

Adaptive Chosen-Message Attack:

  • Attacker can use the signer as an “oracle”
  • Attacker can request signatures on any messages they choose
  • Requests can depend on signer’s public key
  • Later requests can depend on earlier signatures received
  • This is a very strong attack model!

Security Guarantee: Even with all these powers, attacker cannot forge a signature on any message!

๐ŸŽฏ Example: Adaptive Attack Scenario

Attacker’s Goal: Forge Alice’s signature on “Transfer $10,000 to Attacker”

What attacker can do:

  1. Ask Alice to sign: “I am Alice” โ†’ get signature sโ‚
  2. Ask Alice to sign: “Today is Monday” โ†’ get signature sโ‚‚
  3. Analyze sโ‚ and sโ‚‚, look for patterns
  4. Ask Alice to sign: “Transfer $5,000 to Bob” โ†’ get signature sโ‚ƒ
  5. Try to combine signatures mathematically
  6. Ask for more signatures based on what was learned…

With proper RSA signatures: Even after getting millions of signatures, attacker still can’t forge signature on target message!

8. The Complete Picture: Symmetric vs. Public Key Cryptography

Comprehensive Comparison

Security Goal Symmetric Key Setting Public Key Setting
Confidentiality
(Keeping messages secret)
  • Stream Ciphers (RC4, ChaCha20)
  • Block Ciphers (AES) + Modes (CBC, CTR, GCM)
  • Speed: Very Fast โšก
  • Key Size: 128-256 bits
  • RSA-OAEP
  • DHIES/ECIES
  • El Gamal Encryption
  • Speed: Slow ๐ŸŒ
  • Key Size: 2048+ bits
Authenticity & Integrity
(Proving who sent it)
  • Message Authentication Code (MAC)
  • HMAC (with SHA-256)
  • Limitation: No non-repudiation (both parties have same key)
  • Digital Signatures
  • RSA Signatures
  • (EC-)DSA
  • Benefit: Provides non-repudiation!

When to Use What

๐ŸŽฏ Best Practices in Real Systems

Use Public Key Cryptography for:

  • Initial Key Exchange: Establish shared session key
  • Authentication: Verify identity of communicating party
  • Digital Signatures: When non-repudiation is required
  • Small Messages: When message fits in one RSA operation

Use Symmetric Cryptography for:

  • Bulk Data Encryption: Large files, streaming video, etc.
  • Session Encryption: After key exchange completed
  • High-Speed Requirements: Real-time communications
  • MAC Generation: Fast integrity checking

Hybrid Approach (Used by TLS/SSL):

  1. Handshake Phase (PKC):
    • Use RSA or Diffie-Hellman for key exchange
    • Use digital signatures for authentication
    • Establish shared session key
  2. Data Transfer Phase (Symmetric):
    • Use AES with negotiated session key
    • Use HMAC for message integrity
    • Fast and secure!

Real-World Example: HTTPS Connection

๐ŸŒ Example: What Happens When You Visit https://bank.com

Step 1: TLS Handshake (Public Key Crypto)

  1. Server Authentication:
    • Server sends its certificate (contains RSA public key)
    • Certificate is digitally signed by Certificate Authority
    • Browser verifies signature using CA’s public key
    • Browser now trusts server’s public key
  2. Key Exchange:
    • Browser generates random “pre-master secret” (32 bytes)
    • Browser encrypts it with server’s RSA public key
    • Sends to server (only server can decrypt!)
    • Both derive same AES-256 session key from pre-master secret

Step 2: Secure Communication (Symmetric Crypto)

  • All HTTP requests/responses encrypted with AES-256-GCM
  • Each message has HMAC for integrity
  • Can transfer megabytes at high speed
  • Session key changes for each connection (forward secrecy)

Why This Works:

  • โœ“ Slow RSA only used once at start
  • โœ“ Fast AES used for all actual data
  • โœ“ Digital signatures prevent man-in-the-middle
  • โœ“ Best of both worlds!

Summary of Key Concepts

๐Ÿ“Œ Essential Takeaways

1. Public Key Cryptography Solves Key Distribution

  • No need for secure channel to exchange keys
  • Each person needs only one key pair
  • Scales to billions of users

2. RSA Security Relies on Hard Problems

  • Factoring large numbers is computationally infeasible
  • 2048-bit RSA considered secure for near-term
  • Quantum computers may break RSA in future (need post-quantum crypto)

3. Never Use Textbook RSA

  • Always use proper padding (RSA-OAEP for encryption)
  • Always hash messages before signing
  • Real systems use hybrid encryption

4. Digital Signatures โ‰  Encryption

  • Signatures provide authentication and non-repudiation
  • Encryption provides confidentiality
  • Different goals, different constructions
  • Both use public key cryptography but in different ways

5. Hybrid Systems are the Practical Solution

  • Use PKC for key exchange and signatures
  • Use symmetric crypto for bulk data
  • This is how TLS/SSL, PGP, and most secure protocols work

Looking Forward: What’s Next

๐Ÿ”ฎ Topics to Explore Further

  • Diffie-Hellman Key Exchange: How two parties can agree on a key over insecure channel
  • Elliptic Curve Cryptography (ECC): Smaller keys, same security (256-bit ECC โ‰ˆ 3072-bit RSA)
  • Digital Signature Algorithm (DSA): Alternative to RSA signatures
  • Public Key Infrastructure (PKI): How do we know public keys belong to who they claim?
  • Certificate Authorities: Trust model for the internet
  • Post-Quantum Cryptography: Preparing for quantum computers

๐Ÿ’ก Practice Questions & Thought Exercises

Question 1: Key Distribution

A company has 50 employees who all need to communicate securely with each other.

  • a) How many symmetric keys would be needed if they use symmetric cryptography?
  • b) How many keys (total, public + private) would be needed with public key cryptography?
  • c) Which approach is more scalable? Why?
Click for answer
  • a) 50 ร— 49 / 2 = 1,225 symmetric keys
  • b) 50 people ร— 2 keys each = 100 keys total (50 public, 50 private)
  • c) Public key is more scalable: linear growth (2n keys) vs quadratic growth (nยฒ/2 keys)

Question 2: RSA Calculation

Given p = 13, q = 17:

  • a) Compute n
  • b) Compute ฯ†(n)
  • c) Choose a valid e
  • d) Compute corresponding d
Click for answer
  • a) n = 13 ร— 17 = 221
  • b) ฯ†(n) = (13-1)(17-1) = 12 ร— 16 = 192
  • c) e = 5 works (gcd(5, 192) = 1)
  • d) d = 77 (verify: 5 ร— 77 = 385 โ‰ก 1 mod 192)

Question 3: Security Analysis

Explain why each of these is insecure:

  • a) Using textbook RSA to encrypt “Yes” or “No” votes
  • b) Using the same RSA keys for both encryption and signatures
  • c) Using 512-bit RSA in 2026
Click for answer
  • a) Deterministic: attacker can build lookup table of encryptions of “Yes” and “No”, compare with actual vote
  • b) Creates vulnerabilities: signing key should be different from encryption key for security separation
  • c) 512-bit was factored decades ago; 2048+ bits minimum today

๐Ÿ“ Quick Reference Sheet

RSA Formulas

Key Generation:
n = p ร— q
ฯ†(n) = (p-1)(q-1)
e ร— d โ‰ก 1 (mod ฯ†(n))
Encryption:
C = Me mod n
Decryption:
M = Cd mod n
Signature:
s = hash(m)d mod n
Verification:
hash(m) =? se mod n

Key Size Recommendations (2026)

Algorithm Minimum Recommended Long-term
RSA 2048 bits 3072 bits 4096 bits
AES 128 bits 256 bits 256 bits
Hash (SHA) SHA-256 SHA-256 SHA-384/512

Security Notions

  • CPA (Chosen Plaintext Attack): Attacker can encrypt chosen messages
  • CCA (Chosen Ciphertext Attack): Attacker can also decrypt chosen ciphertexts
  • Semantic Security: Ciphertext reveals no information about plaintext
  • Existential Unforgeability: Can’t forge signature on any message